package LeetCodeP;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 *
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 * @Author zengxianlong
 * @Date 2021/12/30 15:06
 * @Version 1.0
 */
public class Solution34 {

   public static void main(String[] args) {
      int[] nums = {5,7,7,8,8,10};
      int target = 8;
      searchRange(nums,target);
   }
   public  static void searchRange(int[] nums,int target){
      int rightBorder = getRightBorder(nums, target);
      int leftBorder = getLeftBorder(nums, target);
      int[] printNums={};
      // 情况一
      if (rightBorder==-2||leftBorder==-2){
         printNums=new int[]{-1,-1};
      }else if (rightBorder-leftBorder>1){
         // 情况三
         printNums=new int[]{leftBorder+1,rightBorder-1};
      }else {
         // 情况二
         printNums=new int[]{-1,-1};
      }
      print(printNums);
   }

   public static  int getRightBorder(int[] nums,int target){
      int left=0;
      int right=nums.length-1;
      int rightBorder=-2; // 记录一下rightBorder没有被赋值的情况
      while (left<=right){
         int middle=left+((right-left)/2);
         if (nums[middle]>target){
            right=middle-1;
         }else {// 寻找右边界，nums[middle] == target的时候更新left
            left=middle+1;
            rightBorder=left;
         }
      }
      return rightBorder;
   }
   private static int getLeftBorder(int[] nums,int target){
      int left=0;
      int right=nums.length-1;
      int leftBorder=-2;// 记录一下leftBorder没有被赋值的情况
      while (left<=right){
         int middle=left+((right-left)/2);
         if (nums[middle]>=target){// 寻找左边界，nums[middle] == target的时候更新right
            right=middle-1;
            leftBorder=right;
         }else {
            left=middle+1;
         }
      }
      return leftBorder;
   }
   private static void print(int[] nums){
      if (nums.length<0){
         return;
      }
      for (int i = 0; i <nums.length; i++) {
         if (i==nums.length-1){
            System.out.print(","+nums[i]);
            break;
         }
         System.out.print(nums[i]);
      }
   }
}
